package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.LinkedList

/*

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html
https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]
 */
class leetcode_94_Kotlin {
    @Test
    fun test_1() {
        val node: TreeNode = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        node.right = n2
        n2.left = n3

        val actual: List<Int> = inorderTraversal(node)
        val expect: List<Int> = arrayListOf(1, 3, 2)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual: List<Int> = inorderTraversal(null)
        val expect: List<Int> = ArrayList<Int>()
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        val actual: List<Int> = inorderTraversal(TreeNode(1))
        val expect: List<Int> = arrayListOf(1)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_4() {
        // 示例2 - https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        val n9 = TreeNode(9)
        n1.left = n2
        n1.right = n3
        n2.left = n4
        n2.right = n5
        n5.left = n6
        n5.right = n7
        n3.right = n8
        n8.left = n9
        val actual: List<Int> = inorderTraversal(n1)
        val expect: List<Int> = arrayListOf(4, 2, 6, 5, 7, 1, 3, 9, 8)
        Assert.assertEquals(expect.toString(), actual.toString())
    }
    private fun inorderTraversal(root: TreeNode?): List<Int> {
//        return inorderTraversal1(root)
//        return inorderTraversal2(root)
        return inorderTraversal3(root)
    }

    private fun inorderTraversal1(root: TreeNode?): List<Int> {
        // 递归
        val list: ArrayList<Int> = ArrayList<Int>()
        traverse(root, list)
        return list
    }

    private fun traverse(node: TreeNode?, list: ArrayList<Int>) {
        // S - N
        // T - N
        if (null == node) {
            return
        }

        traverse(node.left, list)
        list.add(node.`val`)
        traverse(node.right, list)
    }

    private fun inorderTraversal2(root: TreeNode?): List<Int> {
        // 迭代
        val result: ArrayList<Int> = ArrayList<Int>()
        if (null == root) {
            return result
        }
        val stack: LinkedList<TreeNode> = LinkedList<TreeNode>()
        var node: TreeNode? = root
        while (node != null || !stack.isEmpty()) {
            if (null != node) {
                stack.push(node)
                node = node.left
            } else {
                node = stack.pop()
                node = node.right
            }
        }
        return result
    }

    private fun inorderTraversal3(root: TreeNode?): List<Int> {
        val result: ArrayList<Int> = ArrayList<Int>()
        // 1 确定终止条件
        if (null == root) {
            return result
        }
        // 中序遍历：左中右
        // Stack : 右中左
        // 2 初始化栈
        val stack: LinkedList<Pair<TreeNode, Boolean>> = LinkedList<Pair<TreeNode, Boolean>>()
        stack.push(Pair<TreeNode, Boolean>(root, false))

        // 3 利用栈遍历节点
        while (!stack.isEmpty()) {
            val pair: Pair<TreeNode, Boolean> = stack.pop()
            val node = pair.first
            val visited = pair.second
            // 收集节点
            if (visited) {
                result.add(node.`val`)
                continue
            }
            // 确定遍历逻辑：中序遍历
            // 左中右
            // 栈 右中左
            node.right?.let { stack.push(Pair<TreeNode, Boolean>(it, false)) }
            stack.push(Pair<TreeNode, Boolean>(node, true))
            node.left?.let { stack.push(Pair<TreeNode, Boolean>(it, false)) }
        }
        return result
    }
}